/**
 * 简单选择排序:每一趟在待排序元素中选取关键字最小的元素加入到有序子序中
 * 只需要进行n-1趟处理，适用于线性表和链表
 * 
 * 空间复杂度:O(1)
 * 时间复杂度:平均时间复杂度:O(n^2)
 * 算法稳定性:不稳定
 * 
 * 稳定性：不稳定
 */

 void SimpleSelectSort(int A[], int n)
{
	for(int i=0;i<n-1;i++)	//i指向待排序序列的开头位置
	{
		int min=i;			//记录最小元素位置
		for(int j=i+1;j<n;j++)//在A[i,...,n-1]中选择最小的元素
		{
			if(A[j]<min) min=j;//更新最小元素下标
		}
		if(min!=i){
			Swap(A[i],A[min]);	//交换当前待排序序列的头部元素位置和min所致的元素位置
		}   
	} 
}

void Swap(int& a, int& b)
{
	int tmp=a;
	a=b;
	b=tmp;
}